\section{From bounded-round communication complexity to dis\-tri\-bu\-ted algorithm lower bounds}\label{sec:communication_complexity}

%\section{The Simulation Theorem}\label{sec:simulation_theorem}


Consider the following problem. There are two parties that have unbounded computational power. Each party receives a $b$-bit string, for some integer $b\geq 1$, denoted by $\bar{x}$ and $\bar{y}$ in $\{0, 1\}^b$. They both want to together compute $f(\bar{x}, \bar{y})$ for some function $f:\{0, 1\}^b\times \{0, 1\}^b\rightarrow \mathbb{R}$. At the end of the computation, the party receiving $\bar{y}$ has to output the value of $f(\bar{x}, \bar{y})$. We consider two models of communication.


\squishlist
\item {\em $r$-round direct communication:} This is a variant of the standard model in communication complexity (see \cite{NisanW93} and references therein). Two parties can communicate via a bidirectional edge of unlimited bandwidth. We call the party receiving $\bar{x}$ {\em Alice}, and the other party {\em Bob}. Two parties communicate in {\em rounds} where each round Alice sends a message (of any size) to Bob followed by Bob sending a message to Alice.
    % only one party send a message (of any size) to the other party.  %At the end of the process, Bob will output $f(\bar{x}, \bar{y})$.

\item {\em Communication through network $\graph$:} Two parties are distinct nodes in a distributed network $\graph$, for some integers $\Gamma$ and $\Lambda$ and real $\kappa$; all networks in $\graph$ have $\Theta(\kappa\Gamma\Lambda^\kappa)$ nodes and a diameter of $\Theta(\kappa\Lambda)$.
    (This network is described below.) We denote the nodes receiving $\bar{x}$ and $\bar{y}$ by $s$ and $t$, respectively. %At the end of the process, $r$ will output $f(\bar{x}, \bar{y})$.
\squishend

We consider the {\em public coin randomized algorithms} under both models. In particular, we assume that all parties (Alice and Bob in the first model and all nodes in $\graph$ in the second model) share a random bit string of infinite length.
%
For any $\epsilon\geq 0$, we say that a randomized algorithm $\mathcal{A}$ is {\em $\epsilon$-error} if for any input, it outputs the correct answer with probability at least $1-\epsilon$, where the probability is over all possible random bit strings.
%
In the first model, we focus on the message complexity, i.e., the total number of bits exchanged between Alice and Bob, denoted by  $R_{\epsilon}^{r-cc-pub}(f)$. In the second model, we focus on the running time, denoted by $R_\epsilon^{\graph, s, t}(f)$.


Before we describe $\graph$ in detail, we note the following characteristics which will be used in later sections. An essential part of $\graph$ consists of $\Gamma$ {\em paths}, denoted by $\cP^1, \ldots, \cP^\Gamma$ and nodes $s$ and $t$ (see Fig.~\ref{fig:graph}). Every edge induced by this subgraph has infinitely many copies (in other words, infinite capacity). (We let some edges to have infinitely many copies so that we will have a freedom to specify the number of copies later on when we prove Theorem~\ref{thm:rw_lower_bound} in Section~\ref{sec:main_theorem}.
%Note that if a lower bound holds for a graph with some edges having infinitely many copies then it also holds on the same graph when we set the numbers of copies to some specific numbers.)
%
The leftmost and rightmost nodes of each path are adjacent to $s$ and $t$ respectively. Ending nodes on the same side of the path (i.e., leftmost or rightmost nodes) are adjacent to each other.
%
%The following properties of $\graph$ will be proved in Section~\ref{subsec:graph_description}.
%
The following properties of $\graph$ follow from the construction of $\graph$ described in Section~\ref{subsec:graph_description}. %Its proof is in Appendix~\ref{appendix:graph_size_proof}.
%
\begin{lemma}\label{lem:graphsize} For any $\Gamma\geq 1$, $\kappa\geq 1$ and $\Lambda\geq 2$, network $\graph$ has $\Theta(\Gamma\kappa\Lambda^\kappa)$ nodes. Each of its path $\cP^i$ has $\Theta(\kappa\Lambda^{\kappa})$ nodes. Its diameter is $\Theta(\kappa\diam)$.
\end{lemma}
\begin{proof} %[Proof of Lemma~\ref{lem:graphsize}]
It follows from the construction of $\graph$ in Section~\ref{subsec:graph_description} that the number of nodes in each path $\cP^i$ is
$\sum_{j=-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}}^{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}} \phi'_j = \Theta(\kappa\Lambda^\kappa)$ (cf. Eq.~\eqref{eq:sum_phi'}).
%
\note{The real value is between $2\Lambda^\kappa$ and $2(\Lambda^\kappa+\Lambda^{\lfloor\kappa\rfloor})$}
%
Since there are $\Gamma$ paths, the number of nodes in all paths is $\Theta(\Gamma\kappa\Lambda^\kappa)$.
%
Each highway $\cH^i$ has $2\lceil\kappa\rceil\Lambda^i+1$ nodes. Therefore, there are $\sum_{i=1}^{\lfloor\kappa\rfloor} (2\lceil\kappa\rceil\Lambda^i+1)$ nodes in the highways. For $\Lambda\geq 2$, the last quantity is $\Theta(\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor})$.
%
Hence, the total number of nodes is $\Theta(\Gamma\kappa\Lambda^\kappa)$.

To analyze the diameter of $\graph$, observe that each node on any path $\cP^i$ can reach a node in highway $\cH^{\lfloor\kappa\rfloor}$ by traveling through $O(\kappa\Lambda)$ nodes in $\cP^i$. Moreover, any node in highway $\cH^i$ can reach a node in highway $\cH^{i-1}$ by traveling trough $O(\Lambda)$ nodes in $\cH^i$. Finally, there are $O(\kappa\Lambda)$ nodes in $\cH^1$. Therefore, every node can reach any other node in $O(\kappa\Lambda)$ steps by traveling through $\cH^1$. Note that this upper bound is tight since the distance between $s$ and $t$ is $\Omega(\kappa\Lambda)$.
\end{proof}

The rest of this section is devoted to prove Theorem~\ref{thm:cc_to_distributed} which strengthens Theorem~3.1 in \cite{DasSarmaHKKNPPW10}. Recall that Theorem~3.1 in \cite{DasSarmaHKKNPPW10} states that if there is a fast $\epsilon$-error algorithm for computing function $f$ on any network $\graph$, then there is a fast $\epsilon$-error algorithm for Alice and Bob to compute $f$, as follows\footnote{Note that Theorem~3.1 in \cite{DasSarmaHKKNPPW10} is in fact stated on a graph different from $\graph$ but its proof can be easily adapted to prove Theorem~\ref{thm:prev_cc_to_distributed}.}.

\begin{theorem}[Theorem~3.1 in \cite{DasSarmaHKKNPPW10}]\label{thm:prev_cc_to_distributed}
Consider any integers $\Gamma\geq 1$, $\Lambda\geq 2$, real $\kappa\geq 1$ and function $f:\{0, 1\}^{b}\times \{0, 1\}^{b} \rightarrow \mathbb{R}$. Let $r=R_\epsilon^{\graph, s, t}(f)$. For any $b$, if $r \le \kappa\Lambda^\kappa$ then $f$ can be computed by a direct communication protocol using at most $(2\kappa\log{n}) r$ communication bits in total. In other words,
$$R_{\epsilon}^{\infty-cc-pub}(f)\leq (2\kappa\log{n})R_\epsilon^{\graph, s, t}(f)\,.$$
\end{theorem}

The theorem above does not try to optimize number of rounds used by direct communication protocols. In fact, a closer look into the proof of Theorem~3.1 in \cite{DasSarmaHKKNPPW10} reveals that $\tilde \Theta((2\kappa\log{n})R_\epsilon^{\graph, s, t}(f))$ rounds of communication are used.



Theorem~\ref{thm:cc_to_distributed} stated below strengthens the above theorem by making sure that the number of rounds needed in the direct communication is small. In particular, it says that if there is a fast $\epsilon$-error algorithm for computing function $f$ on any network $\graph$, then there is a fast {\em bounded-round} $\epsilon$-error algorithm for Alice and Bob to compute $f$. More importantly, the number of rounds depends on the diameter of $\graph$ (which is $\Theta(\kappa\diam)$), i.e., the larger the network diameter, the smaller the number of rounds.

% THIS THEOREM HAS B IN THE PARAMETER
%\begin{theorem}\label{thm:cc_to_distributed}
%For any integers $\Gamma\geq 1$, $\Lambda\geq 2$, real $\kappa\geq 1$ and function $f:\{0, 1\}^{b}\times \{0, 1\}^{b} \rightarrow \{0, 1\}$, for any $b$, if $R_\epsilon^{\graph, s, t}(f) \le \kappa\Lambda^\kappa$ then $f$ can be computed by a $\frac{8R_\epsilon^{\graph, s, t}(f)}{\kappa\Lambda}$-round direct communication protocol using at most $4BR_\epsilon^{\graph, s, t}(f)$ communication bits in total.
%%In other words, $$R_{\epsilon}^{\frac{8T_\cA}{\lfloor\kappa\rfloor\Lambda}-cc-pub}(f)\leq 2BR_\epsilon^{G, s, t}(f)\,.$$
%\end{theorem}

\begin{theorem}\label{thm:cc_to_distributed}
Consider any integers $\Gamma\geq 1$, $\Lambda\geq 2$, real $\kappa\geq 1$ and function $f:\{0, 1\}^{b}\times \{0, 1\}^{b} \rightarrow \mathbb{R}$. Let $r=R_\epsilon^{\graph, s, t}(f)$. For any $b$, if $r \le \kappa\Lambda^\kappa$ then $f$ can be computed by a $\frac{8r}{\kappa\Lambda}$-round direct communication protocol using at most $(2\kappa\log{n}) r$ communication bits in total. In other words,
$$R_{\epsilon}^{\frac{8R_\epsilon^{\graph, s, t}(f)}{\kappa\Lambda}-cc-pub}(f)\leq (2\kappa\log{n})R_\epsilon^{\graph, s, t}(f)\,.$$
%
%For any integers $\Gamma\geq 1$, $\Lambda\geq 2$, real $\kappa\geq 1$ and function $f:\{0, 1\}^{b}\times \{0, 1\}^{b} \rightarrow \mathbb{R}$, for any $b$, if $R_\epsilon^{\graph, s, t}(f) \le \kappa\Lambda^\kappa$ then $f$ can be computed by a $r$-round direct communication protocol using at most $(2\kappa\log{n}) R_\epsilon^{\graph, s, t}(f)$ communication bits in total, where $r=\frac{8R_\epsilon^{\graph, s, t}(f)}{\kappa\Lambda}$.
%%
%%$\frac{8R_\epsilon^{\graph, s, t}(f)}{\kappa\Lambda}$-round direct communication protocol using at most $(2\kappa\log{n}) R_\epsilon^{\graph, s, t}(f)$ communication bits in total.
%%
%In other words, $$R_{\epsilon}^{\frac{8R_\epsilon^{\graph, s, t}(f)}{\kappa\Lambda}-cc-pub}(f)\leq (2\kappa\log{n})R_\epsilon^{\graph, s, t}(f)\,.$$
\end{theorem}




\newcommand{\PRgraph}{F(\Gamma, \kappa, \Lambda)}
\subsection{Preliminary: the network $\PRgraph$}



%%%%%%%% THIS: Graph \PRgraph %%%%%%%%%%%%%%%



\begin{figure*}[t]
  \centering
  \tiny
    {
    \psfrag{A}[c]{$\cH^1$}
    \psfrag{B}[c]{$\cH^2$}
    \psfrag{C}[c]{$\cP^1$}
    \psfrag{D}[c]{$\cP^2$}
    \psfrag{E}[c]{$\cP^\Gamma$}
    %
    \psfrag{F}{$v^1_{-12, 1}$}
    \psfrag{G}{$v^1_{-12, 2}$}
    \psfrag{H}[r]{$v^1_{-\infty}$}
    \psfrag{I}{$v^2_{-12, 1}$}
    \psfrag{J}{$v^2_{-12, 2}$}
    \psfrag{K}{$v^2_{-\infty}$}
    \psfrag{L}{$v^\Gamma_{-12, 1}$}
    \psfrag{M}{$v^\Gamma_{-12, 2}$}
    \psfrag{N}[r]{$v^\Gamma_{-\infty}$}
    %
    \psfrag{O}{$v^1_{12, 2}$}
    \psfrag{P}{$v^2_{12, 2}$}
    \psfrag{Q}{$v^\Gamma_{12, 2}$}
    \psfrag{R}{$v^1_{12, 1}$}
    \psfrag{U}{$v^2_{12, 1}$}
    \psfrag{V}{$v^\Gamma_{12, 1}$}
    \psfrag{W}{$v^1_{\infty}$}
    \psfrag{X}{$v^\Gamma_{\infty}$}
    %
    \psfrag{S}[c]{$s$}
    \psfrag{T}[c]{$t$}
    %
    \psfrag{a}[c]{$h_{-12}^1$}
    \psfrag{b}[c]{$h_{-10}^1$}
    \psfrag{c}[c]{$h_{-2}^1$}
    \psfrag{d}[c]{$h_{0}^1$}
    \psfrag{e}[c]{$h_{2}^1$}
    \psfrag{f}[c]{$h_{10}^1$}
    \psfrag{g}[c]{$h_{12}^1$}
    %
    \psfrag{h}[c]{$h_{-12}^2$}
    \psfrag{i}[c]{$h_{-11}^2$}
    \psfrag{j}[c]{$h_{-10}^2$}
    \psfrag{k}[c]{$h_{-9}^2$}
    \psfrag{l}[c]{$h_{-2}^2$}
    \psfrag{m}[c]{$h_{-1}^2$}
    \psfrag{n}[c]{$h_{0}^2$}
    \psfrag{o}[c]{$h_{1}^2$}
    \psfrag{p}[c]{$h_{2}^2$}
    \psfrag{q}[c]{$h_{9}^2$}
    \psfrag{r}[c]{$h_{10}^2$}
    \psfrag{s}[c]{$h_{11}^2$}
    \psfrag{t}[l]{$h_{12}^2$}
    %
    \psfrag{u}{$S_{9, 1}$}
    \psfrag{v}{$S_{7, 1}$}
    \psfrag{w}{$S_{-9, 5}$}
    \psfrag{x}{$S_{-9, 4}$}
    \psfrag{y}{$M^{\tau+1}(h^1_{-10}, h^1_{-8})$}
    \psfrag{z}{$M^{\tau+1}(h^2_{-10}, h^2_{-9})$}
    %
    %
    %\hspace{-0.05\linewidth}
    \includegraphics[width=0.9\linewidth]{construction_simpler.eps}
    }
  \caption{\footnotesize An example of $\PRgraph$ where $\Lambda=2$ and $2\leq \kappa<3$. }\label{fig:graph_simpler}
\end{figure*}


Before we describe the construction of $\graph$, we first describe a network called $\PRgraph$ which is a slight modification of the network $F^K_m$ introduced in \cite{PelegR00}. In the next section, we show how we modify $\PRgraph$ to obtain $\graph$.


$\graph$ has three parameters, a real $\kappa\geq 1$ and two integers $\Gamma\geq 1$ and $\Lambda\geq 2$.\footnote{Note that we could restrict $\kappa$ to be an integer here since $F(\Gamma, \kappa, \Lambda)=F(\Gamma, \kappa', \Lambda)$ for any $\Lambda$, $\Gamma$, $\kappa$ and $\kappa'$ such that $\lfloor\kappa\rfloor=\lfloor\kappa'\rfloor$. However, we will need $\kappa$ to be a real when we define $\graph$ so we allow it to be a real here as well to avoid confusion.}
%
The two basic units in the construction of $\PRgraph$  are {\em highways} and {\em paths}.


\paragraph{Highways.} There are $\lfloor\kappa\rfloor$ highways, denoted by $\cH^1$, $\cH^2$, $\ldots$, $\cH^{\lfloor\kappa\rfloor}$. The highway $\cH^i$ is a path of $2\lceil\kappa\rceil\Lambda^i+1$ nodes, i.e.,
\begin{align*}
V(\cH^i) &= \{h_0^i, h_{\pm\Lambda^{\lfloor\kappa\rfloor-i}}^i, h_{\pm2\Lambda^{\lfloor\kappa\rfloor-i}}^i, h_{\pm3\Lambda^{\lfloor\kappa\rfloor-i}}^i, \dots, h_{\pm\lceil\kappa\rceil\Lambda^i\Lambda^{\lfloor\kappa\rfloor-i}}^i\}\\
E(\cH^i) &= \{(h^i_{-(j+1)\Lambda^{\lfloor\kappa\rfloor-i}}, h^i_{-j\Lambda^{\lfloor\kappa\rfloor-i}}), (h^i_{j\Lambda^{\lfloor\kappa\rfloor-i}}, h^i_{(j+1)\Lambda^{\lfloor\kappa\rfloor-i}}) \mid 0 \le j <\lceil\kappa\rceil\Lambda^i\}\,.
\end{align*}

We connect the highways by adding edges between nodes of the same subscripts, i.e., for any $0<i\leq \lfloor\kappa\rfloor$ and $-\lceil\kappa\rceil\Lambda^i \le j \le \lceil\kappa\rceil\Lambda^i$, there is an edge between $h^i_{j\Lambda^{\lfloor\kappa\rfloor-i}}$ and $h^{i+1}_{j\Lambda^{\lfloor\kappa\rfloor-i}}$.

For any $j\neq 0$, let %$-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor} \leq j\leq \lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}$, define
\begin{align}
\phi_j=1 ~~\mbox{if $j=0$, and}~~ \phi'_j =\Lambda ~~\mbox{otherwise.}\label{eq:phi'_PelegR}
\end{align}

We use $\phi'_j$ to specify the number of nodes in the paths (defined next), i.e., each path will have $\sum_{j=-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}}^{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}} \phi'_j$ nodes. Note that
\begin{align}
\sum_{j=-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}}^{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}} \phi'_j
= (2\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}+1) \Lambda
= \Theta(\kappa\Lambda^{\lfloor\kappa\rfloor+1}).\label{eq:sum_phi'_PelegR}
\end{align}


\paragraph{Paths.}
There are $\Gamma$ paths, denoted by $\cP^1, \cP^2, \ldots, \cP^{\Gamma}$. To construct each path, we first construct its subpaths as follows. For each node $h^{\lfloor\kappa\rfloor}_j$ in $\cH^{\lfloor\kappa\rfloor}$ and any $0< i\leq \Gamma$, we create a subpath of $\cP^i$, denoted by $\cP^i_j$, having $\phi'_j$ nodes. Denote nodes in $\cP^i_j$ in order by $v^i_{j, 1}, v^i_{j, 2}, \ldots, v^i_{j, \phi'_j}$. We connect these paths together to form $\cP^i_j$, i.e., for any $j\geq 0$, we create edges $(v^i_{j, \phi'_j}, v^i_{j+1, 1})$ and $(v^i_{-j, \phi'_{-j}}, v^i_{-(j+1), 1})$. Let
$$v^i_{-\infty}=v^i_{-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}, \phi'_{-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}}} ~~~\mbox{and}~~~ v^i_{\infty}=v^i_{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}, \phi'_{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}}}\,.$$
These two nodes can be thought of as the leftmost and rightmost nodes of path $\cP^i$. We connect the paths together by adding edges between the leftmost (rightmost, respectively) nodes in the paths, i.e., for any $i$ and $i'$, we add edges $(v^i_{-\infty}, v^{i'}_{-\infty})$ ($(v^i_{\infty}, v^{i'}_{\infty})$, respectively).
%


We connect the highways and paths by adding an edge from each node $h^{\lfloor\kappa\rfloor}_j$ to $v^i_{j, 1}$.
%
We also create nodes $s$ and $t$ and connect $s$ ($t$, respectively) to all nodes $v^i_{-\infty}$ ($v^i_\infty$, respectively).
%
See Fig.~\ref{fig:graph_simpler} for an example.






\subsection{Description of $\graph$}\label{subsec:graph_description}


We now modify $\PRgraph$ to obtain $\graph$. Again, $\graph$ has three parameters, a real $\kappa\geq 1$ and two integers $\Gamma\geq 1$ and $\Lambda\geq 2$. The two basic units in the construction of $\graph$ are {\em highways} and {\em paths}. The highways are defined in exactly the same way as before. The main modification is the definition of $\phi'$ (cf. Eq.~\eqref{eq:phi'_PelegR}) which affects the number of nodes in the subpaths $\cP^i_j$ of each path $\cP^i$.

\paragraph{Definition of $\phi'$.} First, for a technical reason in the proof of Theorem~\ref{thm:cc_to_distributed}, we need $\phi'_j$ to be small when $|j|$ is small. Thus, we define the following notation $\phi$. For any $j$, define %$-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor} \leq j\leq \lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}$, define
%\[\phi(h^{\lfloor\kappa\rfloor}_j)=\left\lfloor \frac{|j|}{\Lambda^{\lfloor\kappa\rfloor-1}}\right\rfloor + 1\,.\]
\[\phi_j=\left\lfloor \frac{|j|}{\Lambda^{\lfloor\kappa\rfloor-1}}\right\rfloor + 1\,.\]
%
Note that $\phi_j$ can be viewed as the number of nodes in $\cH_1$ with subscripts between $0$ and $j$, i.e.,
%
%Observe that $\phi_j$ is the number of nodes in $\cH_1$ with indices between $0$ and $j$, i.e.,
%
%$$\phi_j=|\{h^1_{j'} \mid 0\leq j'\leq j\}|,~~\forall j\geq 0, ~~~\mbox{and}~~~ \phi_j=|\{h^1_{j'} \mid j\leq j'\leq 0\}|,~~\forall j<0\,.$$
\begin{equation*}
\phi_j=
\begin{cases}
|\{h^1_{j'} \mid 0\leq j'\leq j\}| &\mbox{if $j\geq 0$}\\
|\{h^1_{j'} \mid j\leq j'\leq 0\}| & \mbox{if $j<0$}\,.
\end{cases}
\end{equation*}
%
We now define $\phi'$ as follows. For any $j\geq 0$, let
%$\phi'(h^{\lfloor\kappa\rfloor}_j)$ and $\phi'(h^{\lfloor\kappa\rfloor}_{-j})$ to be
%
%$\max(1, \Lambda^\kappa-\sum_{j'>j} \phi(h^{\lfloor\kappa\rfloor}_{j'}))$.
%\[\phi'(h^{\lfloor\kappa\rfloor}_j) = \phi'(h^{\lfloor\kappa\rfloor}_{-j}) = \min\left(\phi(h^{k'}_{r}), \max(1, \Lambda^\kappa-\sum_{j'>j} \phi(h^{\lfloor\kappa\rfloor}_{j'}))\right)\,.\]
%
\[\phi'_j = \phi'_{-j} = \min\left\{\phi_j, \max(1, \lceil\lceil\kappa\rceil\Lambda^\kappa\rceil-\sum_{j'>j} \phi_{j'})\right\}\,.\]
%
%When the parameters are clear from the context, we use $\phi'_j$ to denote $\phi'(h^{\lfloor\kappa\rfloor}_j)$.
%
The reason we define $\phi'$ this way is that we use it to specify the number of nodes in the paths (as described in the previous section) and we want to be able to control this number precisely. In particular, while each path $\cP^i$ in $\PRgraph$ has $\Theta(\kappa\Lambda^{\lfloor\kappa\rfloor+1})$ nodes (cf. Eq.~\eqref{eq:sum_phi'_PelegR}), the number of nodes in each path in $\graph$ is %$\sum_{j=-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}}^{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}} \phi'_j$ nodes. Note that
\begin{align}
\sum_{j=-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}}^{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}} \phi'_j = \Theta(\kappa\Lambda^\kappa).\label{eq:sum_phi'}
\end{align}
%
We need this precision so that we can deal with any value of $\ell$ when we prove Theorem~\ref{thm:rw_lower_bound} in Section~\ref{sec:main_theorem}.


%%%%%%%% THIS: Graph \graph %%%%%%%%%%%%%%%

\begin{figure*}
  \centering
  \tiny
    {
    \psfrag{A}[c]{$\cH^1$}
    \psfrag{B}[c]{$\cH^2$}
    \psfrag{C}[c]{$\cP^1$}
    \psfrag{D}[c]{$\cP^2$}
    \psfrag{E}[c]{$\cP^\Gamma$}
    %
    \psfrag{F}{$v^1_{-12, 1}$}
    \psfrag{G}{$v^1_{-12, 2}$}
    \psfrag{H}{$v^1_{-\infty}$}
    \psfrag{I}{$v^2_{-12, 1}$}
    \psfrag{J}{$v^2_{-12, 2}$}
    \psfrag{K}{$v^2_{-\infty}$}
    \psfrag{L}{$v^\Gamma_{-12, 1}$}
    \psfrag{M}{$v^\Gamma_{-12, 2}$}
    \psfrag{N}{$v^\Gamma_{-\infty}$}
    %
    \psfrag{O}{$v^1_{12, 2}$}
    \psfrag{P}{$v^2_{12, 2}$}
    \psfrag{Q}{$v^\Gamma_{12, 2}$}
    \psfrag{R}{$v^1_{12, 1}$}
    \psfrag{U}{$v^2_{12, 1}$}
    \psfrag{V}{$v^\Gamma_{12, 1}$}
    \psfrag{W}{$v^1_{\infty}$}
    \psfrag{X}{$v^\Gamma_{\infty}$}
    %
    \psfrag{S}[c]{$s$}
    \psfrag{T}[c]{$t$}
    %
    \psfrag{a}[c]{$h_{-12}^1$}
    \psfrag{b}[c]{$h_{-10}^1$}
    \psfrag{c}[c]{$h_{-2}^1$}
    \psfrag{d}[c]{$h_{0}^1$}
    \psfrag{e}[c]{$h_{2}^1$}
    \psfrag{f}[c]{$h_{10}^1$}
    \psfrag{g}[c]{$h_{12}^1$}
    %
    \psfrag{h}[c]{$h_{-12}^2$}
    \psfrag{i}[c]{$h_{-11}^2$}
    \psfrag{j}[c]{$h_{-10}^2$}
    \psfrag{k}[c]{$h_{-9}^2$}
    \psfrag{l}[c]{$h_{-2}^2$}
    \psfrag{m}[c]{$h_{-1}^2$}
    \psfrag{n}[c]{$h_{0}^2$}
    \psfrag{o}[c]{$h_{1}^2$}
    \psfrag{p}[c]{$h_{2}^2$}
    \psfrag{q}[c]{$h_{9}^2$}
    \psfrag{r}[c]{$h_{10}^2$}
    \psfrag{s}[c]{$h_{11}^2$}
    \psfrag{t}[c]{$h_{12}^2$}
    %
    \psfrag{u}{$S_{9, 1}$}
    \psfrag{v}{$S_{7, 1}$}
    \psfrag{w}{$S_{-9, 5}$}
    \psfrag{x}{$S_{-9, 4}$}
    \psfrag{y}{$M^{\tau+1}(h^1_{-10}, h^1_{-8})$}
    \psfrag{z}{$M^{\tau+1}(h^2_{-10}, h^2_{-9})$}
    %
    %
    %\hspace{-0.05\linewidth}
    \includegraphics[width=\linewidth]{construction.eps}
    }
  \caption{\footnotesize An example of $\graph$ where $\kappa=2.5$ and $\Lambda=2$. The dashed edges (in red) have one copy while other edges have infinitely many copies. Note that $\phi'_{10}=4$ and thus there are $4$ nodes in each subpath $\cP^i_{10}$, for all $i$. Note also that $\phi'_{10}$ is less than $\phi_{10}$ which is $6$.}\label{fig:graph}
\end{figure*}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% This part is moved to the previous section
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%
%
%\paragraph{Highways.} There are $\lfloor\kappa\rfloor$ highways, denoted by $\cH^1$, $\cH^2$, $\ldots$, $\cH^{\lfloor\kappa\rfloor}$. The highway $\cH^i$ is a path of $2\lceil\kappa\rceil\Lambda^i+1$ nodes, i.e.,
%\begin{align*}
%V(\cH^i) &= \{h_0^i, h_{\pm\Lambda^{\lfloor\kappa\rfloor-i}}^i, h_{\pm2\Lambda^{\lfloor\kappa\rfloor-i}}^i, h_{\pm3\Lambda^{\lfloor\kappa\rfloor-i}}^i, \\
%&\ \ \ \dots, h_{\pm\lceil\kappa\rceil\Lambda^i\Lambda^{\lfloor\kappa\rfloor-i}}^i\}\\
%E(\cH^i) &= \{(h^i_{-(j+1)\Lambda^{\lfloor\kappa\rfloor-i}}, h^i_{-j\Lambda^{\lfloor\kappa\rfloor-i}}), (h^i_{j\Lambda^{\lfloor\kappa\rfloor-i}}, h^i_{(j+1)\Lambda^{\lfloor\kappa\rfloor-i}}) \\
%& \ \ \ \mid 0 \le j <\lceil\kappa\rceil\Lambda^i\}\,.
%\end{align*}
%
%%$$V(\cH^i)= \{h_0^i, h_{\pm\Lambda^{\lfloor\kappa\rfloor-i}}^i, h_{\pm2\Lambda^{\lfloor\kappa\rfloor-i}}^i, h_{\pm3\Lambda^{\lfloor\kappa\rfloor-i}}^i, \dots, h_{\pm\lceil\kappa\rceil\Lambda^i\Lambda^{\lfloor\kappa\rfloor-i}}^i\}\quad\mbox{and,}$$
%%%
%%$$E(\cH^i) = \{(h^i_{-(j+1)\Lambda^{\lfloor\kappa\rfloor-i}}, h^i_{-j\Lambda^{\lfloor\kappa\rfloor-i}}), (h^i_{j\Lambda^{\lfloor\kappa\rfloor-i}}, h^i_{(j+1)\Lambda^{\lfloor\kappa\rfloor-i}}) \mid 0 \le j <\lceil\kappa\rceil\Lambda^i\}\,.$$
%%
%We connect the highways by adding edges between nodes of the same subscripts, i.e., for any $0<i\leq \lfloor\kappa\rfloor$ and $-\lceil\kappa\rceil\Lambda^i \le j \le \lceil\kappa\rceil\Lambda^i$, there is an edge between $h^i_{j\Lambda^{\lfloor\kappa\rfloor-i}}$ and $h^{i+1}_{j\Lambda^{\lfloor\kappa\rfloor-i}}$.
%
%%\paragraph{Labels and Active Nodes.}
%For any $-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor} \leq j\leq \lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}$, define
%%\[\phi(h^{\lfloor\kappa\rfloor}_j)=\left\lfloor \frac{|j|}{\Lambda^{\lfloor\kappa\rfloor-1}}\right\rfloor + 1\,.\]
%\[\phi_j=\left\lfloor \frac{|j|}{\Lambda^{\lfloor\kappa\rfloor-1}}\right\rfloor + 1\,.\]
%%
%Note that $\phi_j$ can be viewed as the number of nodes in $\cH_1$ with subscripts between $0$ and $j$, i.e.,
%%
%%Observe that $\phi_j$ is the number of nodes in $\cH_1$ with indices between $0$ and $j$, i.e.,
%%
%%$$\phi_j=|\{h^1_{j'} \mid 0\leq j'\leq j\}|,~~\forall j\geq 0, ~~~\mbox{and}~~~ \phi_j=|\{h^1_{j'} \mid j\leq j'\leq 0\}|,~~\forall j<0\,.$$
%\begin{equation*}
%\phi_j=
%\begin{cases}
%|\{h^1_{j'} \mid 0\leq j'\leq j\}| &\mbox{if $j\geq 0$}\\
%|\{h^1_{j'} \mid j\leq j'\leq 0\}| & \mbox{if $j<0$}\,.
%\end{cases}
%\end{equation*}
%%
%For any $j\geq 0$, we also define
%%$\phi'(h^{\lfloor\kappa\rfloor}_j)$ and $\phi'(h^{\lfloor\kappa\rfloor}_{-j})$ to be
%%
%%$\max(1, \Lambda^\kappa-\sum_{j'>j} \phi(h^{\lfloor\kappa\rfloor}_{j'}))$.
%%\[\phi'(h^{\lfloor\kappa\rfloor}_j) = \phi'(h^{\lfloor\kappa\rfloor}_{-j}) = \min\left(\phi(h^{k'}_{r}), \max(1, \Lambda^\kappa-\sum_{j'>j} \phi(h^{\lfloor\kappa\rfloor}_{j'}))\right)\,.\]
%%
%\[\phi'_j = \phi'_{-j} = \min\left\{\phi_j, \max(1, \lceil\lceil\kappa\rceil\Lambda^\kappa\rceil-\sum_{j'>j} \phi_{j'})\right\}\,.\]
%%
%%When the parameters are clear from the context, we use $\phi'_j$ to denote $\phi'(h^{\lfloor\kappa\rfloor}_j)$.
%%
%We use $\phi'_j$ to specify the number of nodes in the paths (defined next), i.e., each path will have $\sum_{j=-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}}^{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}} \phi'_j$ nodes. Note that
%\begin{align}
%\sum_{j=-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}}^{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}} \phi'_j = \Theta(\kappa\Lambda^\kappa).\label{eq:sum_phi'}
%\end{align}


%\paragraph{Paths.}
%There are $\Gamma$ paths, denoted by $\cP^1, \cP^2, \ldots, \cP^{\Gamma}$. To construct each path, we first construct its subpaths as follows. For each node $h^{\lfloor\kappa\rfloor}_j$ in $\cH^{\lfloor\kappa\rfloor}$ and any $0< i\leq \Gamma$, we create a subpath of $\cP^i$, denoted by $\cP^i_j$, having $\phi'_j$ nodes. Denote nodes in $\cP^i_j$ in order by $v^i_{j, 1}, v^i_{j, 2}, \ldots, v^i_{j, \phi'_j}$. We connect these paths together to form $\cP^i_j$, i.e., for any $j\geq 0$, we create edges $(v^i_{j, \phi'_j}, v^i_{j+1, 1})$ and $(v^i_{-j, \phi'_{-j}}, v^i_{-(j+1), 1})$. Let
%$$v^i_{-\infty}=v^i_{-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}, \phi'_{-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}}} ~~~\mbox{and}~~~ v^i_{\infty}=v^i_{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}, \phi'_{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}}}\,.$$
%These two nodes can be thought of as the leftmost and rightmost nodes of path $\cP^i$. We connect the paths together by adding edges between the leftmost (rightmost, respectively) nodes in the paths, i.e., for any $i$ and $i'$, we add edges $(v^i_{-\infty}, v^{i'}_{-\infty})$ ($(v^i_{\infty}, v^{i'}_{\infty})$, respectively).
%%
%
%
%We connect the highways and paths by adding an edge from each node $h^{\lfloor\kappa\rfloor}_j$ to $v^i_{j, 1}$.
%%
%We also create nodes $s$ and $t$ and connect $s$ ($t$, respectively) to all nodes $v^i_{-\infty}$ ($v^i_\infty$, respectively).

Finally, we make infinite copies of every edge except highway edges, i.e., those in $\cup_{i=1}^{\lfloor\kappa\rfloor} E(\cH^i)$. (In other words, we make them have infinite capacity). As mentioned earlier, we do this so that we will have a freedom to specify the number of copies later on when we prove Theorem~\ref{thm:rw_lower_bound} in Section~\ref{sec:main_theorem}. Observe that if Theorem~\ref{thm:cc_to_distributed} then it also holds when we set the numbers of edge copies in $\graph$ to some specific numbers.
%
Fig.~\ref{fig:graph} shows an example of $\graph$.

%Observe the following properties of $\graph$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


% THIS FIGURE COMBINES EVERYTHING IN ONE FIGURE
%
%\begin{figure}
%  \centering
%  \tiny
%    {
%    \psfrag{A}[c]{$\cH^1$}
%    \psfrag{B}[c]{$\cH^2$}
%    \psfrag{C}[c]{$\cP^1$}
%    \psfrag{D}[c]{$\cP^2$}
%    \psfrag{E}[c]{$\cP^\Gamma$}
%    %
%    \psfrag{F}{$v^1_{-9, 4}$}
%    \psfrag{G}{$v^1_{-9, 5}$}
%    \psfrag{H}{$v^1_{-\infty}$}
%    \psfrag{I}{$v^2_{-9, 4}$}
%    \psfrag{J}{$v^2_{-9, 5}$}
%    \psfrag{K}{$v^2_{-\infty}$}
%    \psfrag{L}{$v^\Gamma_{-9, 4}$}
%    \psfrag{M}{$v^\Gamma_{-9, 5}$}
%    \psfrag{N}{$v^\Gamma_{-\infty}$}
%    %
%    \psfrag{O}{$v^1_{9, 1}$}
%    \psfrag{P}{$v^2_{9, 1}$}
%    \psfrag{Q}{$v^\Gamma_{9, 1}$}
%    \psfrag{R}{$v^1_{7, 1}$}
%    \psfrag{U}{$v^2_{7, 1}$}
%    \psfrag{V}{$v^\Gamma_{7, 1}$}
%    \psfrag{W}{$v^1_{\infty}$}
%    \psfrag{X}{$v^\Gamma_{\infty}$}
%    %
%    \psfrag{S}[c]{$s$}
%    \psfrag{T}[c]{$t$}
%    %
%    \psfrag{a}[c]{$h_{-10}^1$}
%    \psfrag{b}[c]{$h_{-8}^1$}
%    \psfrag{c}[c]{$h_{-2}^1$}
%    \psfrag{d}[c]{$h_{0}^1$}
%    \psfrag{e}[c]{$h_{2}^1$}
%    \psfrag{f}[c]{$h_{8}^1$}
%    \psfrag{g}[c]{$h_{10}^1$}
%    %
%    \psfrag{h}[c]{$h_{-10}^2$}
%    \psfrag{i}[c]{$h_{-9}^2$}
%    \psfrag{j}[c]{$h_{-8}^2$}
%    \psfrag{k}[c]{$h_{-7}^2$}
%    \psfrag{l}[c]{$h_{-2}^2$}
%    \psfrag{m}[c]{$h_{-1}^2$}
%    \psfrag{n}[c]{$h_{0}^2$}
%    \psfrag{o}[c]{$h_{1}^2$}
%    \psfrag{p}[c]{$h_{2}^2$}
%    \psfrag{q}[c]{$h_{7}^2$}
%    \psfrag{r}[c]{$h_{8}^2$}
%    \psfrag{s}[c]{$h_{9}^2$}
%    \psfrag{t}[c]{$h_{10}^2$}
%    %
%    \psfrag{u}{$S_{9, 1}$}
%    \psfrag{v}{$S_{7, 1}$}
%    \psfrag{w}{$S_{-9, 5}$}
%    \psfrag{x}{$S_{-9, 4}$}
%    \psfrag{y}{$M^{\tau+1}(h^1_{-10}, h^1_{-8})$}
%    \psfrag{z}{$M^{\tau+1}(h^2_{-10}, h^2_{-9})$}
%    %
%    %
%    %\hspace{-0.05\linewidth}
%    \includegraphics[width=\linewidth]{G_Gamma_kappa25_Lambda2_2.eps}
%    }
%  \caption{\footnotesize An example of a network in $\graph$ where $\kappa=2.5$ and $\Lambda=2$. The dashed edges (in red) have one copy while other edges have infinitely many copies. Four boxes show an example of iteration 1 of round 9 in the proof of Theorem~\ref{thm:cc_to_distributed}, when Alice sends messages. Initially, Alice and Bob know $C^{\tau}_{9, 1}$ and $C^\tau_{-9, 5}$, respectively (assuming Alice and Bob already simulate $\cA$ for $\tau$ steps). Then, Alice sends $M^{\tau+1}(h^2_{-10}, h^2_{-9})$ and $M^{\tau+1}(h^1_{-10}, h^1_{-8})$ to Bob. Finally, Alice and Bob compute $C^{\tau+1}_{7, 1}$ and $C^{\tau+1}_{-9, 4}$, respectively.}\label{fig:graph}\label{fig:simulation}
%\end{figure}
%



%\begin{proof}[Proof of Lemma~\ref{lem:graphsize}]
%The number of nodes in each path $\cP^i$ is
%$\sum_{j=-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}}^{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}} \phi'_j = \Theta(\kappa\Lambda^\kappa)$ (cf. Eq.~\eqref{eq:sum_phi'}).
%%
%\note{The real value is between $2\Lambda^\kappa$ and $2(\Lambda^\kappa+\Lambda^{\lfloor\kappa\rfloor})$}
%%
%Since there are $\Gamma$ paths, the number of nodes in all paths is $\Theta(\Gamma\kappa\Lambda^\kappa)$.
%%
%Each highway $\cH^i$ has $2\lceil\kappa\rceil\Lambda^i+1$ nodes. Therefore, there are $\sum_{i=1}^{\lfloor\kappa\rfloor} (2\lceil\kappa\rceil\Lambda^i+1)$ nodes in the highways. For $\Lambda\geq 2$, the last quantity is $\Theta(\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor})$.
%%
%Hence, the total number of nodes is $\Theta(\Gamma\kappa\Lambda^\kappa)$.
%
%To analyze the diameter of $\graph$, observe that each node on any path $\cP^i$ can reach a node in highway $\cH^{\lfloor\kappa\rfloor}$ by traveling through $O(\kappa\Lambda)$ nodes in $\cP^i$. Moreover, any node in highway $\cH^i$ can reach a node in highway $\cH^{i-1}$ by traveling trough $O(\Lambda)$ nodes in $\cH^i$. Finally, there are $O(\kappa\Lambda)$ nodes in $\cH^1$. Therefore, every node can reach any other node in $O(\kappa\Lambda)$ steps by traveling through $\cH^1$. Note that this upper bound is tight since the distance between $s$ and $t$ is $\Omega(\kappa\Lambda)$.
%\end{proof}




\subsection{Terminologies}

For any numbers $i$, $j$, $i'$, and $j'$, we say that $(i', j')\geq (i, j)$ if $i'>i$ or ($i'=i$ and $j'\geq j$).
%
For any $-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}\leq i\leq \lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}$ and $1\leq j\leq \phi'_i$, define the {\em $(i, j)$-set} as
%
%
\begin{equation*}
S_{i, j} =
\begin{cases}
\{h^x_{i'}\ |\ 1\leq x\leq \kappa,\ i'\leq i\}\cup\ \{v^x_{i', j'}\ |\  1\leq x\leq \Gamma,\ (i, j)\geq (i', j')\} \cup \{s\} &\text{if $i\geq 0$}\\
\{h^x_{i'}\ |\ 1\leq x\leq \kappa,\ i'\geq i\}\cup\ \{v^x_{i', j'}\ |\  1\leq x\leq \Gamma,\ (-i, j)\geq (-i', j')\} \cup \{r\} &\text{if $i<0$}\,.
\end{cases}
\end{equation*}
%
See Fig.~\ref{fig:simulation} for an example. For convenience, for any $i>0$, let 
$$S_{i, 0}=S_{i-1, \phi'_{i-1}}~~~~\mbox{and}~~~~S_{-i, 0}=S_{-(i-1), \phi'_{-(i-1)}}\,,$$ 
and, for any $j$, let 
$$S_{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}+1, j}=S_{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}, \phi'_{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}}}~~~~\mbox{and}~~~~S_{-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}-1, j}=S_{-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}, \phi'_{-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}}}\,.$$

%For convenience, for any $i$, let
%
%\[S_{i, 0}=S_{i-1, \phi'_i} ~~~\mbox{and}~~~ S_{-i, 0}=S_{-i+1, \phi'_{-i}} ~~~\mbox{and}~~~ S_{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}+1, j}=S_{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}+1, \phi'_{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}}} ~~~\mbox{and}~~~ S_{-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}-1, j}=S_{-\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}+1, \phi'_{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}}}\,.\]



%%%%%%%%%%%%%%%%%%% OLD FIGURE %%%%%%%%%%%%%%%%%%%%%%

%\begin{figure}
%  \centering
%  \scriptsize
%    {
%    \psfrag{A}[c]{$\cH^1$}
%    \psfrag{B}[c]{$\cH^2$}
%    \psfrag{C}[c]{$\cP^1$}
%    \psfrag{D}[c]{$\cP^2$}
%    \psfrag{E}[c]{$\cP^\Gamma$}
%    %
%    \psfrag{F}[c]{$C^{t+1}_{-3, 1}$}
%    \psfrag{H}[c]{$C^t_{-3, 2}$}
%    \psfrag{G}[c]{$C^{t}_{3, 1}$}
%    \psfrag{I}[c]{$C^{t+1}_{1, 1}$}
%    %\psfrag{F}[c]{$S_{-3, 2}$}
%    %\psfrag{H}[c]{$S_{-3, 1}$}
%    %\psfrag{G}[c]{$S_{3, 1}$}
%    %\psfrag{I}[c]{$S_{1, 1}$}
%    \psfrag{S}[c]{$s$}
%    \psfrag{T}[c]{$t$}
%    %
%    \psfrag{a}[c]{$h_{-4}^1$}
%    \psfrag{b}[c]{$h_{-2}^1$}
%    \psfrag{c}[c]{$h_0^1$}
%    \psfrag{d}[c]{$h_2^1$}
%    \psfrag{e}[c]{$h_4^1$}
%    %
%    \psfrag{f}{$h_{-4}^2$}
%    \psfrag{g}{$h_{-3}^2$}
%    \psfrag{h}{$h_{-2}^2$}
%    \psfrag{i}{$h_{0}^2$}
%    \psfrag{j}{$h_{3}^2$}
%    \psfrag{k}{$h_{4}^2$}
%    %
%    \psfrag{l}{$v_{-3, 2}^1$}
%    \psfrag{m}{$v_{-3, 1}^1$}
%    \psfrag{n}{$v_{-2, 1}^1$}
%    \psfrag{o}{$v_{3, 1}^1$}
%    \psfrag{p}{$v_{1, 1}^1$}
%    \psfrag{q}{$M^{t+1}(h^1_{-4}, h^1_{-2})$}
%    \psfrag{r}{$M^{t+1}(h^2_{-4}, h^2_{-3})$}
%    %
%    \includegraphics[width=0.95\linewidth]{G_Gamma_kappa25_Lambda2_simulate_iter1.eps}
%    }
%  \caption{\footnotesize An example of iteration 1 of round 3 when Alice sends messages. Initially, Alice and Bob know $C^{\tau}_{3, 1}$ and $C^\tau_{-3, 2}$, respectively (assuming Alice and Bob already simulate $\cA$ for $\tau$ steps). Then, Alice sends $M^{\tau+1}(h^2_{-4}, h^2_{-3})$ and $M^{\tau+1}(h^1_{-4}, h^1_{-2})$ to Bob. Finally, Alice and Bob compute $C^{\tau+1}_{1, 1}$ and $C^{\tau+1}_{-3, 1}$, respectively.}\label{fig:simulation}
%\end{figure}


Let $\mathcal{A}$ be any {\em deterministic} distributed algorithm run on $\graph$ for computing a function $f$. Fix any input strings $\bar{x}$ and $\bar{y}$ given to $s$ and $t$ respectively. Let $\varphi_\cA(\bar{x}, \bar{y})$ denote the execution of $\mathcal{A}$ on $\bar{x}$ and $\bar{y}$. Denote the {\em state} of the node $v$ at the end of time $\tau$ during the execution $\varphi_\cA(\bar{x}, \bar{y})$ by $\sigma_\cA(v, \tau, \bar{x}, \bar{y})$. Let $\sigma_\cA(v, 0, \bar{x}, \bar{y})$ be the state of the node $v$ before the execution $\varphi_\cA(\bar{x}, \bar{y})$ begins. Note that $\sigma_\cA(v, 0, \bar{x}, \bar{y})$ is independent of the input if $v\notin \{s, t\}$, depends only on $\bar{x}$ if $v=s$ and depends only on $\bar{y}$ if $v=t$. Moreover, in two different executions $\varphi_\cA(\bar{x}, \bar{y})$ and $\varphi_\cA(\bar{x}', \bar{y}')$, a node reaches the same state at time $\tau$ (i.e., $\sigma_\cA(v, \tau, \bar{x}, \bar{y})=\sigma_\cA(v, \tau, \bar{x}', \bar{y}')$) if and only if it receives the same sequence of messages on each of its incoming links.


For a given set of nodes $U=\{v_1, \ldots, v_\ell\}\subseteq V$, a {\em configuration}
%
%%%%%% Remove to save space %%%%%%%%%%%
\[C_\cA(U, \tau, \bar{x}, \bar{y}) = <\sigma_\cA(v_1, \tau, \bar{x}, \bar{y}), \ldots, \sigma_\cA(v_\ell, \tau, \bar{x}, \bar{y})>\]
%
%$C_\cA(U, \tau, \bar{x}, \bar{y})$ = $<\sigma_\cA(v_1, \tau, \bar{x}, \bar{y})$, $\ldots$, $\sigma_\cA(v_\ell, \tau, \bar{x}, \bar{y})>$
%
is a vector of the states of the nodes of $U$ at the end of time $\tau$ of the execution $\varphi_\cA(\bar{x}, \bar{y})$.
%
%
From now on, to simplify notations, when $\cA$, $\bar{x}$ and $\bar{y}$ are clear from the context, we use $C^\tau_{i, j}$ to denote $C_\cA(S_{i, j}, \tau, \bar{x}, \bar{y})$.
%

%%%%%%%%%%%%%%%%%%% FIGURE %%%%%%%%%%%%%%%%%%%%

\begin{figure*}
  \centering
  \tiny
    {
    \psfrag{A}[c]{$\cH^1$}
    \psfrag{B}[c]{$\cH^2$}
    \psfrag{C}[c]{$\cP^1$}
    \psfrag{D}[c]{$\cP^2$}
    \psfrag{E}[c]{$\cP^\Gamma$}
    %
    \psfrag{F}{$v^1_{-11, 4}$}
    \psfrag{G}{$v^1_{-11, 5}$}
    \psfrag{H}{$S_{1, 1}$}
    \psfrag{I}{$v^2_{-11, 4}$}
    \psfrag{J}{$v^2_{-11, 5}$}
    \psfrag{K}{$v^2_{-\infty}$}
    \psfrag{L}{$v^\Gamma_{-11, 4}$}
    \psfrag{M}{$v^\Gamma_{-11, 5}$}
    \psfrag{N}{$v^\Gamma_{-\infty}$}
    %
    \psfrag{O}{$v^1_{11, 1}$}
    \psfrag{P}{$v^2_{11, 1}$}
    \psfrag{Q}{$v^\Gamma_{11, 1}$}
    \psfrag{R}{$v^1_{9, 1}$}
    \psfrag{U}{$v^2_{9, 1}$}
    \psfrag{V}{$v^\Gamma_{9, 1}$}
    \psfrag{W}{$S_{-11, 0}=S_{-10, 4}$}
    \psfrag{X}{$v^\Gamma_{\infty}$}
    %
    \psfrag{S}[c]{$s$}
    \psfrag{T}[c]{$t$}
    %
    \psfrag{a}[c]{$h_{-12}^1$}
    \psfrag{b}[c]{$h_{-10}^1$}
    \psfrag{c}[c]{$h_{-2}^1$}
    \psfrag{d}[c]{$h_{0}^1$}
    \psfrag{e}[c]{$h_{2}^1$}
    \psfrag{f}[c]{$h_{10}^1$}
    \psfrag{g}[c]{$h_{12}^1$}
    %
    \psfrag{h}[c]{$h_{-12}^2$}
    \psfrag{i}[c]{$h_{-11}^2$}
    \psfrag{j}[c]{$h_{-10}^2$}
    \psfrag{k}[c]{$h_{-9}^2$}
    \psfrag{l}[c]{$h_{-2}^2$}
    \psfrag{m}[c]{$h_{-1}^2$}
    \psfrag{n}[c]{$h_{0}^2$}
    \psfrag{o}[c]{$h_{1}^2$}
    \psfrag{p}[c]{$h_{2}^2$}
    \psfrag{q}[c]{$h_{9}^2$}
    \psfrag{r}[c]{$h_{10}^2$}
    \psfrag{s}[c]{$h_{11}^2$}
    \psfrag{t}[c]{$h_{12}^2$}
    %
    \psfrag{u}{$S_{11, 1}$}
    \psfrag{v}{$S_{9, 1}$}
    \psfrag{w}{$S_{-11, 6}$}
    \psfrag{x}{$S_{-11, 5}$}
    \psfrag{y}{$M^{8}(h^1_{-12}, h^1_{-10})$}
    \psfrag{z}{$M^{8}(h^2_{-12}, h^2_{-11})$}
    %
    %
    \includegraphics[width=\linewidth]{simulation.eps}
    }
%  \caption{\footnotesize An example of round $9$ in the proof of Theorem~\ref{thm:cc_to_distributed}. Before iteration $I_{9, A, 1}$ begins, Alice and Bob know $C^{6}_{9, 1}$ and $C^6_{-9, 5}$, respectively (since Alice and Bob already simulated $\cA$ for $6$ steps). Then, Alice computes and sends $M^{7}(h^2_{-10}, h^2_{-9})$ and $M^{7}(h^1_{-10}, h^1_{-8})$ to Bob.  Alice and Bob then compute $C^{7}_{7, 1}$ and $C^{7}_{-9, 4}$, respectively, at the end of iteration $I_{9, A, 1}$. After they repeat this process for four more times, i.e. Alice sends $M^{8}(h^2_{-10}, h^2_{-9})$, $M^{9}(h^2_{-10}, h^2_{-9})$, $M^{10}(h^2_{-10}, h^2_{-9})$, $M^{11}(h^2_{-10}, h^2_{-9})$ $M^{8}(h^1_{-10}, h^1_{-8})$, $M^{9}(h^1_{-10}, h^1_{-8})$, $M^{10}(h^1_{-10}, h^1_{-8})$ and $M^{11}(h^1_{-10}, h^1_{-8})$,  Bob will be able to compute $C^{11}_{-9, 0}=C^{11}_{-8, 5}$, respectively. Note that Alice is able to compute $C^8_{5, 1}$, $C^9_{3, 1}$, and $C^{10}_{3, 1}$ without receiving any messages from Bob so she can compute and send the previously mentioned messages.}\label{fig:simulation}
%
  \caption{\footnotesize An example of round $11$ in the proof of Theorem~\ref{thm:cc_to_distributed} (see detail in Example~\ref{ex:protocol}).} \label{fig:simulation}
\end{figure*}





\subsection{Proof of Theorem~\ref{thm:cc_to_distributed}}
%\danupon{To do: Highlight the difference from the previous proof}
%
%
Let $G=\graph$. Let $f$ be the function in the theorem statement. Let $\mathcal{A}_\epsilon$ be any $\epsilon$-error distributed algorithm for computing $f$ on $G$. Fix a random string $\bar{r}$ used by $\mathcal{A}_\epsilon$ (shared by all nodes in $G$) and consider the {\em deterministic} algorithm $\mathcal{A}$ run on the input of $\mathcal{A}_\epsilon$ and the fixed random string $\bar{r}$.
%
Let $T_{\mathcal{A}}$ be the worst case running time of algorithm $\mathcal{A}$ (over all inputs).
We only consider $T_\mathcal{A}\leq \kappa\Lambda^{\kappa}$, as assumed in the theorem statement.
%
We show that Alice and Bob, when given $\bar{r}$ as the public random string, can simulate $\mathcal{A}$ using $(2\kappa \log{n})T_\mathcal{A}$ communication bits in $8T_\mathcal{A}/(\kappa\Lambda)$ rounds, as follows. (We provide an example in the end of this section.)



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\paragraph{Rounds, Phases, and Iterations.}
For convenience, we will name the rounds backward, i.e., Alice and Bob start at round $\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}$ and proceed to round $\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}-1$, $\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}-2$, and so on.
%
Each round is divided into two {\em phases}, i.e., when Alice sends messages and Bob sends messages (recall that Alice sends messages first in each iteration). Each phase of round $r$ is divided into $\phi'_r$ {\em iterations}. Each iteration simulates one round of algorithm $\cA$.
%
We call the $i^{th}$ iteration of round $r$ when Alice (Bob, respectively) sends messages the {\em iteration $I_{r, A, i}$} ($I_{r, B, i}$, respectively). Therefore, in each round $r$ we have the following order of iterations: $I_{r, A, 1}$, $I_{r, A, 2}$, $\ldots$, $I_{r, A, \phi'_r}$, $I_{r, B, 1}$, $\ldots$, $I_{r, B, \phi'_r}$. For convenience, we refer to the time before communication begins as round $\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}+1$ and let $I_{r, A, 0}=I_{r+1, A, \phi'_{r+1}}$ and $I_{r, B, 0}=I_{r+1, B, \phi'_{r+1}}$.


Our goal is to simulate one round of algorithm $\cA$ per iteration. That is, after iteration $I_{r, B, i}$ finishes, we will finish the $(\sum_{r'=r+1}^{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}} \phi'_{r'}+i)^{th}$ round of algorithm $\cA$. Specifically, we let
%
$$t_r=\sum_{r'=r+1}^{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}} \phi'_{r'}$$
and our goal is to construct a protocol with properties as in the following lemma.

\begin{lemma}\label{lem:after_iteration} There exists a protocol such that there are at most $\kappa\log n$ bits sent in each iteration and satisfies the following properties. For any $r\geq 0$ and $0\leq i\leq \phi'_r$,
%\squishlist
\begin{enumerate}
\item after $I_{r, A, i}$ finishes, Alice and Bob know $C^{t_r+i}_{r-i\Lambda^{\lfloor\kappa\rfloor-1}, 1}$ and $C^{t_r+i}_{-r, \phi'_{-r}-i}$, respectively, and \label{property:alice}
\item after $I_{r, B, i}$ finishes, Alice and Bob know $C^{t_r+i}_{r, \phi'_{r}-i}$ and $C^{t_r+i}_{-r+i\Lambda^{\lfloor\kappa\rfloor-1}, 1}$, respectively. \label{property:bob}
%\squishend
\end{enumerate}
\end{lemma}

\begin{proof}%[Proof of Lemma~\ref{lem:after_iteration}]
We first argue that the properties hold for iteration $I_{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}+1, A, 0}$, i.e., before Alice and Bob starts communicating. After round $r=\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}$ starts, Alice can compute $C^0_{r+1, 0}=C^0_{r+1, 1}=C^0_{r, \phi'_{r}}$ which contains the states of all nodes in $\graph$ except $t$. She can do this because every node except $s$ and $t$ has the same state regardless of the input and the state of $s$ depends only on her input string $\bar{x}$.  Similarly, Bob can compute $C^0_{-(r+1), 0}=C^0_{-(r+1), 1}=C^0_{r, \phi'_{r}}$  which depends only on his input $\bar{y}$.

Now we show that, if the lemma holds for any iteration $I_{r, A, i-1}$ then it also holds for iteration $I_{r, A, i}$ as well. Specifically, we show that if Alice and Bob know $C^{t_r+i-1}_{r-(i-1)\Lambda^{\lfloor\kappa\rfloor-1}, 1}$ and $C^{t_r+i-1}_{-r, \phi'_{-r}-(i-1)}$, respectively, then they will know $C^{t_r+i}_{r-i\Lambda^{\lfloor\kappa\rfloor-1}, 1}$ and $C^{t_r+i}_{-r, \phi'_{-r}-i}$, respectively, after Alice sends at most $\kappa\log n$ messages.

First we show that Alice can compute $C^{t_r+i}_{r-i\Lambda^{\lfloor\kappa\rfloor-1}, 1}$ without receiving any message from Bob. Recall that Alice can compute $C^{t_r+i}_{r-i\Lambda^{\lfloor\kappa\rfloor-1}, 1}$ if she knows
%
\squishlist
\item $C^{t_r+i-1}_{r-i\Lambda^{\lfloor\kappa\rfloor-1}, 1}$, and
\item all messages sent to all nodes in $S_{r-i\Lambda^{\lfloor\kappa\rfloor-1}, 1}$ at time $t_r+i$ of algorithm $\cA$.
\squishend
%
By assumption, Alice knows $C^{t_r+i-1}_{r-(i-1)\Lambda^{\lfloor\kappa\rfloor-1}, 1}$ which implies that she knows $C^{t_r+i-1}_{r-i\Lambda^{\lfloor\kappa\rfloor-1}, 1}$ since
$$S_{r-i\Lambda^{\lfloor\kappa\rfloor-1}, 1} \subseteq S_{r-(i-1)\Lambda^{\lfloor\kappa\rfloor-1}, 1}\,.$$
%
Moreover, observe that all neighbors of all nodes in  $S_{r-i\Lambda^{\lfloor\kappa\rfloor-1},1}$ are in $S_{r-(i-1)\Lambda^{\lfloor\kappa\rfloor-1}, 1}$. Thus, Alice can compute all messages sent to all nodes in $S_{r-i\Lambda^{\lfloor\kappa\rfloor-1}, 1}$ at time $t_r+i$ of algorithm $\cA$. Therefore, Alice can compute $C^{t_r+i}_{r+i\Lambda^{\lfloor\kappa\rfloor-1}, 1}$ without receiving any message from Bob.

Now we show that Bob can compute $C^{t_r+i}_{-r, \phi'_{-r}-i}$ by receiving at most $\kappa\log n$ bits from Alice and use the knowledge of $C^{t_r+i-1}_{-r, \phi'_{-r}-i+1}$. Note that Bob can compute $C^{t_r+i}_{-r, \phi'_{-r}-i}$ if he knows
\squishlist
\item $C^{t_r+i-1}_{-r, \phi'_{-r}-i}$, and
\item all messages sent to all nodes in $S_{-r, \phi'_{-r}-i}$ at time $t_r+i$ of algorithm $\cA$.
\squishend
%
By assumption, Bob knows $C^{t_r+i-1}_{-r, \phi'_{-r}-i+1}$ which implies that he knows $C^{t_r+i-1}_{-r, \phi'_{-r}-i}$ since $S_{-r, \phi'_{-r}-i}\subseteq S_{-r, \phi'_{-r}-i+1}$.
%
Moreover, observe that all neighbors of all nodes in $S_{-r, \phi'_{-r}-i}$ are in $S_{-r, \phi'_{-r}-i+1}$, except
%
\begin{align*}
&h^{\lfloor\kappa\rfloor}_{-(r+1)}, h^{\lfloor\kappa\rfloor-1}_{-(\lfloor r/\Lambda\rfloor+1)}, \ldots, h^{\lfloor\kappa\rfloor-i}_{-(\lfloor r/\Lambda^i\rfloor+1)}, \ldots, h^1_{-(\lfloor r/\Lambda^{\lfloor\kappa\rfloor-1}\rfloor+1)}.
\end{align*}
%
%\begin{quote}
%$h^{\lfloor\kappa\rfloor}_{-(r+1)}$, $h^{\lfloor\kappa\rfloor-1}_{-(\lfloor r/\Lambda\rfloor+1)}$, $\ldots$, $h^{\lfloor\kappa\rfloor-i}_{-(\lfloor r/\Lambda^i\rfloor+1)}$, $\ldots$, $h^1_{-(\lfloor r/\Lambda^{\lfloor\kappa\rfloor-1}\rfloor+1)}$.
%\end{quote}
%
In other words, Bob can compute all messages sent to all nodes in $S_{-r, \phi'_{-r}-i}$ at time $t_r+i$ except
%
\begin{align*}
&M^{t_r+i}(h^{\lfloor\kappa\rfloor}_{-(r+1)}, h^{\lfloor\kappa\rfloor}_{-r}), \ldots, M^{t_r+i}(h^{\lfloor\kappa\rfloor-i}_{-(\lfloor r/\Lambda^i\rfloor+1)}, h^{\lfloor\kappa\rfloor-i}_{-\lfloor r/\Lambda^i\rfloor}),
\ldots, M^{t_r+i}(h^1_{-(\lfloor r/\Lambda^{\lfloor\kappa\rfloor-1}\rfloor+1)}, h^1_{-(\lfloor r/\Lambda^{\lfloor\kappa\rfloor-1}\rfloor})
\end{align*}
%
%\begin{quote}
%$M^{t_r+i}(h^{\lfloor\kappa\rfloor}_{-(r+1)}, h^{\lfloor\kappa\rfloor}_{-r})$, $\ldots$, $M^{t_r+i}(h^{\lfloor\kappa\rfloor-i}_{-(\lfloor r/\Lambda^i\rfloor+1)}, h^{\lfloor\kappa\rfloor-i}_{-\lfloor r/\Lambda^i\rfloor})$, $\ldots$, $M^{t_r+i}(h^1_{-(\lfloor r/\Lambda^{\lfloor\kappa\rfloor-1}\rfloor+1)}, h^1_{-(\lfloor r/\Lambda^{\lfloor\kappa\rfloor-1}\rfloor})$
%\end{quote}
%
where $M^{t_r+i}(u, v)$ is the message sent from $u$ to $v$ at time $t_r+i$ of algorithm $\cA$. Observe further that Alice can compute these messages because she knows $C^{t_r+i-1}_{r-(i-1)\Lambda^{\lfloor\kappa\rfloor-1}, 1}$ which contains the states of
\begin{align*}
h^{\lfloor\kappa\rfloor}_{-(r+1)}, \ldots, h^{\lfloor\kappa\rfloor-i}_{-(\lfloor r/\Lambda^i\rfloor+1)}, \ldots,~~~h^1_{-(\lfloor r/\Lambda^{\lfloor\kappa\rfloor-1}\rfloor+1)}
\end{align*}
%
%$h^{\lfloor\kappa\rfloor}_{-(r+1)}$, $\ldots$, $h^{\lfloor\kappa\rfloor-i}_{-(\lfloor r/\Lambda^i\rfloor+1)}$, $\ldots$, $h^1_{-(\lfloor r/\Lambda^{\lfloor\kappa\rfloor-1}\rfloor+1)}$
%
at time $t_r+i-1$. (In particular, $C^{t_r+i-1}_{r-(i-1)\Lambda^{\lfloor\kappa\rfloor-1}, 1}$ is a superset of $C^{t_r+i-1}_{0, 1}$ which contains the states of $h^{\lfloor\kappa\rfloor}_{-(r+1)}$, $\ldots$, $h^1_{-(\lfloor r/\Lambda^{\lfloor\kappa\rfloor-1}\rfloor+1)}$.) So, Alice can send these messages to Bob and Bob can compute $C^{t_r+i}_{-r, \phi'_{-r}-i}$ at the end of the iteration. Each of these messages contains at most $\log n$ bits since each of them corresponds to a message sent on one edge. Therefore, Alice sends at most $\kappa \log n$ bits to Bob in total. This shows the first property.


After Alice finishes sending messages, the two parties will switch their roles and a similar protocol can be used to show that the second property, i.e., if the lemma holds for any iteration $I_{r, B, i-1}$ then it also holds for iteration $I_{r, B, i}$ as well. That is, if Alice and Bob know $C^{t_r+i-1}_{r, \phi'_{r}-(i-1)}$ and $C^{t_r+i-1}_{-r+(i-1)\Lambda^{\lfloor\kappa\rfloor-1}, 1}$, respectively, then Bob can send $\kappa \log n$ bits to Alice so that they can compute $C^{t_r+i}_{r, \phi'_{r}-i}$ and $C^{t_r+i}_{-r+i\Lambda^{\lfloor\kappa\rfloor-1}, 1}$, respectively.
\end{proof}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%Before we describe a protocol that satisfies Lemma~\ref{lem:after_iteration}, we first prove Theorem~\ref{thm:cc_to_distributed}, assuming this lemma.

%We are now ready to prove Theorem~\ref{thm:cc_to_distributed}.

%\begin{proof}[Proof of Theorem~\ref{thm:cc_to_distributed}]% assuming Lemma~\ref{lem:after_iteration}]
Let $P$ be the protocol as in Lemma~\ref{lem:after_iteration}. Alice and Bob will run protocol $P$ until round $r'$, where $r'$ is the largest number such that $t_{r'}+\phi'_{r'}\geq T_\cA$.
%
Lemma~\ref{lem:after_iteration} implies that after iteration $I_{r', B, T_\cA-t_{r'}}$, Bob knows $$C^{t_{-r'}+T_\cA-t_{r'}}_{-r', \phi'_{-r'}-T_\cA+t_{r'}}=C^{T_\cA}_{-r', \phi'_{-r'}-T_\cA+t_{r'}}$$
(note that $\phi'_{-r'}-T_\cA+t_{r'}\geq 0$).
%
%Therefore, after round $r'$, Alice and Bob know $C^{T_\cA}_{r', \phi'_{r'}}$ and $C^{T_\cA}_{-r', \phi'_{-r'}}$, respectively.
%
In particular, Bob knows the state of node $t$ at time $T_\cA$, i.e., he knows $\sigma_\cA(t, T_\cA, \bar{x}, \bar{y})$. Thus, Bob can output the output of $\cA$ which is output from $t$.

Since $\mathcal{A}_\epsilon$ is $\epsilon$-error, the probability (over all possible shared random strings) that $\mathcal{A}$ outputs the correct value of $f(\bar{x}, \bar{y})$ is at least $1-\epsilon$. Therefore, the communication protocol run by Alice and Bob is $\epsilon$-error as well. The number of rounds is bounded as in the following claim.

\begin{claim}
If algorithm $\cA$ finishes in time $T_\cA\leq \lceil\kappa\rceil\Lambda^\kappa$ then $r'>\lceil\kappa\rceil\Lambda^\kappa-8T_\cA/(\lceil\kappa\rceil\Lambda)$. In other words, the number of rounds Alice and Bob need to simulate $\cA$ is $8T_\cA/(\lceil\kappa\rceil\Lambda)$
%If algorithm $\cA$ finishes in time $T_\cA\leq \Lambda^\kappa$, then the number of rounds Alice and Bob need to simulate $\cA$ is $8T_\cA/(\lceil\kappa\rceil\Lambda)$. %In other words, $r'>\Lambda^\kappa-8T_\cA/\Lambda$
\end{claim}
\begin{proof}
Let $R^*=8T_\cA/(\lceil\kappa\rceil\Lambda)$ and let $r^*=\Lambda^{\lfloor\kappa\rfloor}-R^*+1$. Assume for the sake of contradiction that Alice and Bob need more than $R^*$ rounds. This means that $r'<r^*$.
%
%for each round $r$, they simulate $\cA$ for $\phi'_r$ steps. Thus, the total number of steps of $\cA$ that are simulated by Alice and Bob up to round $r^*$ is
%
%$\sum_{r=r^*}^{\Lambda^{\lfloor\kappa\rfloor}} \phi'_r$.
%
%
Alice and Bob requiring more than $R^*$ rounds implies that %$\sum_{r\geq r^*} \phi'_r < T_\cA$ which is at most $\Lambda^\kappa$.
%
%$$\sum_{r=r^*}^{\Lambda^{\lfloor\kappa\rfloor}} \phi'_r < T_\cA\leq \Lambda^\kappa\,.$$
\begin{align}
\sum_{r=r^*}^{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}} \phi'_r = t_{r^*}+\phi'_{r^*} < T_\cA \leq \lceil\kappa\rceil\Lambda^\kappa\,.\label{eq:round_bound}
\end{align}
%
It follows that for any $r\geq r^*$,
\begin{align}
\phi'_r &= \min\left(\phi(h^{k'}_{r}), \max(1, \lceil\lceil\kappa\rceil\Lambda^\kappa\rceil-\sum_{r'>r} \phi_{r'})\right) \label{eq:a1}\\
&= \phi_r \label{eq:a2}\\%&&\mbox{(because $\sum_{r\geq r^*} \phi'_r< \lceil\kappa\rceil\Lambda^\kappa$)}\\
&= \left\lfloor \frac{r}{\Lambda^{\lfloor\kappa\rfloor-1}}\right\rfloor +1 \label{eq:a3}%&&\mbox{(by definition of $\phi_r$).}
\end{align}
where Eq.~\eqref{eq:a1} follows from the definition of $\phi'_r$, Eq.~\eqref{eq:a2} is because $\sum_{r\geq r^*} \phi'_r< \lceil\kappa\rceil\Lambda^\kappa$, and Eq.~\eqref{eq:a3} is by the definition of $\phi_r$.
%
%\begin{align*}
%\phi'_r &= \min\left(\phi(h^{k'}_{r}), \max(1, \lceil\lceil\kappa\rceil\Lambda^\kappa\rceil-\sum_{r'>r} \phi_{r'})\right) &&\mbox{(by definition of $\phi'_r$)}\\
%&= \phi_r &&\mbox{(because $\sum_{r\geq r^*} \phi'_r< \lceil\kappa\rceil\Lambda^\kappa$)}\\
%&= \left\lfloor \frac{r}{\Lambda^{\lfloor\kappa\rfloor-1}}\right\rfloor +1 &&\mbox{(by definition of $\phi_r$).}
%\end{align*}
%
%
Therefore, the total number of steps that can be simulated by Alice and Bob up to round $r^*$ is
\begin{align*}
\sum_{r=r^*}^{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}} \phi'_r & = \sum_{r=r^*}^{\lceil\kappa\rceil\Lambda^{\lfloor\kappa\rfloor}} \left(\left\lfloor \frac{r}{\Lambda^{\lfloor\kappa\rfloor-1}}\right\rfloor +1\right)\\
&\geq \Lambda^{\lfloor\kappa\rfloor-1} \sum_{i=1}^{\lfloor R^*/\Lambda^{\lfloor\kappa\rfloor-1}\rfloor} (\lceil\kappa\rceil\Lambda-i)\\
&\geq \Lambda^{\lfloor\kappa\rfloor-1} \cdot \frac{\lfloor R^*/\Lambda^{\lfloor\kappa\rfloor-1}\rfloor (\lceil\kappa\rceil\Lambda-1)}{2}\\
&\geq \frac{R^*\lceil\kappa\rceil\Lambda}{8}\\
&\geq T_\cA
\end{align*}
%
contradicting Eq.~\eqref{eq:round_bound}.
\end{proof}

%In other words, $r'>\Lambda^\kappa-8T_\cA/\Lambda\geq 0$. Thus,
%

Since there are at most $\kappa \log n$ bits sent in each iteration and Alice and Bob runs $P$ for $T_\cA$ iterations, the total number of bits exchanged is at most $(2\kappa\log n)T_\mathcal{A}$. This completes the proof of Theorem~\ref{thm:cc_to_distributed}.
%\end{proof}

%\paragraph{Example}
\begin{example}\label{ex:protocol}
Fig.~\ref{fig:simulation} shows an example of the protocol we use above. Before iteration $I_{11, A, 1}$ begins, Alice and Bob know $C^{7}_{11, 1}$ and $C^7_{-11, 5}$, respectively (since Alice and Bob already simulated $\cA$ for $\phi'_{12}=7$ steps in round $12$). Then, Alice computes and sends $M^{8}(h^2_{-12}, h^2_{-11})$ and $M^{8}(h^1_{-12}, h^1_{-10})$ to Bob.  Alice and Bob then compute $C^{8}_{11, 1}$ and $C^{8}_{-11, 6}$, respectively, at the end of iteration $I_{11, A, 1}$. After they repeat this process for five more times, i.e. Alice sends
%
$$M^{9}(h^2_{-12}, h^2_{-11}), M^{10}(h^2_{-12}, h^2_{-11}), \ldots, M^{13}(h^2_{-12}, h^2_{-11}), ~~~\mbox{and}~~~$$
$$M^{9}(h^1_{-12}, h^1_{-10}), M^{10}(h^1_{-12}, h^1_{-10}), \ldots, M^{13}(h^1_{-12}, h^1_{-10})\,,$$
%
Bob will be able to compute $C^{13}_{-11, 0}=C^{13}_{-10, 4}$. Note that Alice is able to compute $C^8_{9, 1}$, $C^9_{7, 1}$, $\ldots$, $C^{12}_{1, 1}$ without receiving any messages from Bob so she can compute and send the previously mentioned messages to Bob.
\end{example}











